package codetop.microsoft.T105;

import util.TreeNode;

/**
 * @Author: 18362
 * @Create: 2022-08-14 23:49:08 星期日
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return build(preorder, inorder, 0, preorder.length-1, 0, inorder.length-1);
    }

    private TreeNode build(int[] pre, int[] in, int prel, int prer, int inl, int inr) {
        if (prel > prer)
            return null;
        TreeNode root = new TreeNode(pre[prel]);
        int k = 0;
        for (int i=inl; i<=inr; ++i) {
            if (in[i] == pre[prel]) {
                k = i;
                break;
            }
        }
        root.left = build(pre, in, prel+1, prel+k-inl, inl, k-1);
        root.right = build(pre, in, prel+k-inl+1, prer, k+1, inr);
        return root;
    }
}